package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * c
 * dp
 * 1187. 使数组严格递增
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/15 10:51
 */
public class MakeArrayIncreasing {


    public static void main(String[] args) {
        MakeArrayIncreasing test = new MakeArrayIncreasing();

        // 1
//        int[] arr1 = {1, 5, 3, 6, 7};
//        int[] arr2 = {1, 2, 3, 4};

        // 2
//        int[] arr1 = {1, 5, 3, 6, 7};
//        int[] arr2 = {1, 3, 4};

        // -1
//        int[] arr1 = {1, 5, 3, 6, 7};
//        int[] arr2 = {1, 6, 3, 3};

        //
        int[] arr1 = Utils.getArr(2, 1, 100000);
        int[] arr2 = Utils.getArr(1, 1, 100000);

        int i = test.makeArrayIncreasing(arr1, arr2);
        System.out.println(i);
    }

    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        Arrays.sort(arr2);
        int m = arr1.length;
        int n = arr2.length;
        int[] values = new int[n + 1];
        int[] counts = new int[n + 1];
        int[] lastValues = new int[n + 1];
        int[] lastCounts = new int[n + 1];
        int v = arr1[0];
        add(arr2, lastValues, v);
        addCount(lastValues, lastCounts, v);
        int lastMin = lastValues[0];
        for (int i = 1; i < m; i++) {
            v = arr1[i];
            add(arr2, values, v);
            int count = Integer.MAX_VALUE;
            int lastIndex = 0;
            int itemMin = Integer.MAX_VALUE;
            for (int j = 0; j <= n; j++) {
                int t = values[j];
                if (t <= lastMin) {
                    counts[j] = count;
                    continue;
                }
                itemMin = Math.min(itemMin, t);
                while (lastIndex <= n && lastValues[lastIndex] < t) {
                    count = Math.min(count, lastCounts[lastIndex]);
                    lastIndex++;
                }
                counts[j] = t == v ? count : count + 1;
            }
            lastMin = itemMin;
            if (lastMin == Integer.MAX_VALUE) {
                return -1;
            }
            System.arraycopy(counts, 0, lastCounts, 0, counts.length);
            System.arraycopy(values, 0, lastValues, 0, counts.length);
        }
        int min = Integer.MAX_VALUE;
        for (int lastCount : lastCounts) {
            min = Math.min(min, lastCount);
        }
        return min;
    }

    private void add(int[] arr, int[] values, int v) {
        int length = arr.length;
        int index = 0;
        if (v <= arr[0]) {
            values[index++] = v;
        }
        for (int i = 0; i < length; i++) {
            values[index++] = arr[i];
            if (arr[i] < v && i + 1 < length && arr[i + 1] >= v) {
                values[index++] = v;
            }
        }
        if (index == length) {
            values[index] = v;
        }
    }

    private void addCount(int[] values, int[] counts, int v) {
        int length = values.length;
        for (int i = 0; i < length; i++) {
            if (values[i] != v) {
                counts[i] = 1;
            }
        }
    }

}
